home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / src / exampleCode / 3Dmodeling / smooth.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-02  |  5.4 KB  |  252 lines
  1. /*
  2.  * Copyright 1992, 1993, 1994, Silicon Graphics, Inc.
  3.  * All Rights Reserved.
  4.  *
  5.  * This is UNPUBLISHED PROPRIETARY SOURCE CODE of Silicon Graphics, Inc.;
  6.  * the contents of this file may not be disclosed to third parties, copied or
  7.  * duplicated in any form, in whole or in part, without the prior written
  8.  * permission of Silicon Graphics, Inc.
  9.  *
  10.  * RESTRICTED RIGHTS LEGEND:
  11.  * Use, duplication or disclosure by the Government is subject to restrictions
  12.  * as set forth in subdivision (c)(1)(ii) of the Rights in Technical Data
  13.  * and Computer Software clause at DFARS 252.227-7013, and/or in similar or
  14.  * successor clauses in the FAR, DOD or NASA FAR Supplement. Unpublished -
  15.  * rights reserved under the Copyright Laws of the United States.
  16.  */
  17.  
  18. /* Tom Davis -- 1992 */
  19.  
  20. /* This code takes a solid defined by quadrilaterals, finds those
  21.  * with similar coordinates, and constructs normal vectors by averaging
  22.  * the normals to the individual quads meeting at the point.  The
  23.  * routines count on having the floating point values exactly equal --
  24.  * it doesn't do a "within epsilon" test.  To use it, make sure that
  25.  * any points at common vertices have EXACTLY the same floating point
  26.  * coordinates.  All (well, at least most) of the code in this directory
  27.  * satisfies those conditions.
  28.  */
  29.  
  30. #include <stdio.h>
  31. #include "3d.h"
  32.  
  33. #define CHUNKCOUNT    500
  34.  
  35. typedef struct chunklist {
  36.     struct chunklist    *next;
  37.     long        *data;
  38. } chunklist_t;
  39.  
  40. chunklist_t    *chunklist = 0;
  41.  
  42. static long *addchunks(long length)
  43. {
  44.     chunklist_t    *c = (chunklist_t *)malloc(sizeof(chunklist_t));
  45.     long    i, *l;
  46.  
  47.     c->next = chunklist;
  48.     chunklist = c;
  49.     c->data = l = (long *)malloc(4*length*CHUNKCOUNT);
  50.     for (i = 0; i < CHUNKCOUNT-2; i++)
  51.     l[i*length] = (long)&l[(i+1)*length];
  52.     l[(CHUNKCOUNT-2)*length] = 0;
  53.     return l;
  54. }
  55.  
  56. static void freechunkdata()
  57. {
  58.     chunklist_t *c;
  59.  
  60.     while (c = chunklist) {
  61.     free(c->data);
  62.     chunklist = c->next;
  63.     free(c);
  64.     }
  65. }
  66.  
  67. typedef struct polylist {
  68.     struct polylist    *next;
  69.     long        data;
  70. } polylist_t;
  71.  
  72. typedef struct vertex3d {
  73.     struct vertex3d    *next;
  74.     float        v[3];
  75.     float        n[3];    /* averaged normal */
  76.     polylist_t        *polys;
  77. } vertex3d_t;
  78.  
  79. typedef struct quad {
  80.     struct quad        *next;
  81.     struct vertex3d    *v0, *v1, *v2, *v3;
  82.     float        n[3];
  83. } quad_t;
  84.  
  85. #define VERTHASHSIZE    1693
  86.  
  87. vertex3d_t    *verthashtab[VERTHASHSIZE];
  88. quad_t        *quadlist = 0;
  89.  
  90. static long hashvert(float v[3])
  91. {
  92.     long h;
  93.  
  94.     h = (*(long *)&v[0]) + ((*(long *)&v[1])>>1) + ((*(long *)&v[2])>>5);
  95.     h &= 0x7ffffff;
  96.     h = h % VERTHASHSIZE;
  97.     return h;
  98. }
  99.  
  100. vertex3d_t    *vlist = 0;
  101.  
  102. static vertex3d_t    *newvertex3d()
  103. {
  104.     vertex3d_t    *v;
  105.  
  106.     if (vlist == 0) vlist = (vertex3d_t *)addchunks((sizeof(vertex3d_t))>>2);
  107.     v = vlist;
  108.     vlist = vlist->next;
  109.     v->next = 0;
  110.     v->polys = 0;
  111.     return v;
  112. }
  113.  
  114. quad_t    *qlist = 0;
  115.  
  116. static quad_t    *newquad()
  117. {
  118.     quad_t    *q;
  119.  
  120.     if (qlist == 0) qlist = (quad_t *)addchunks((sizeof(quad_t))>>2);
  121.     q = qlist;
  122.     qlist = qlist->next;
  123.     q->next = quadlist;
  124.     quadlist = q;
  125.     return q;
  126. }
  127.  
  128. polylist_t    *plist = 0;
  129.  
  130. static polylist_t    *newpolylist()
  131. {
  132.     polylist_t    *p;
  133.  
  134.     if (plist == 0) plist = (polylist_t *)addchunks((sizeof(polylist_t))>>2);
  135.     p = plist;
  136.     plist = plist->next;
  137.     return p;
  138. }
  139.  
  140. static vertex3d_t *findverthash(float v[3])
  141. {
  142.     long    h = hashvert(v);
  143.     vertex3d_t    *vt;
  144.  
  145.     vt = verthashtab[h];
  146.  
  147.     while (vt) {
  148.     if (vt->v[0] == v[0] && vt->v[1] == v[1] && vt->v[2] == v[2])
  149.         return vt;
  150.     vt = vt->next;
  151.     }
  152.     return 0;
  153. }
  154.  
  155. static void appendpoly(long p, vertex3d_t *v)
  156. {
  157.     polylist_t    *pl = newpolylist();
  158.  
  159.     pl->data = p;
  160.     pl->next = v->polys;
  161.     v->polys = pl;
  162. }
  163.  
  164. static vertex3d_t *addvertex(float v[3])
  165. {
  166.     vertex3d_t    *vt = newvertex3d();
  167.     long h = hashvert(v);
  168.  
  169.     vt->v[0] = v[0]; vt->v[1] = v[1]; vt->v[2] = v[2];
  170.     vt->next = verthashtab[h];
  171.     verthashtab[h] = vt;
  172.     return vt;
  173. }
  174.  
  175. static void cleanupsmooth()
  176. {
  177.     long    i;
  178.  
  179.     freechunkdata();
  180.     for (i = 0; i < VERTHASHSIZE; i++) verthashtab[i] = 0;
  181.     chunklist = 0;
  182.     quadlist = 0;
  183.     qlist = 0;
  184.     vlist = 0;
  185.     plist = 0;
  186. }
  187.  
  188. void addquad(float v0[3], float v1[3], float v2[3], float v3[3], float n[3])
  189. {
  190.     quad_t    *q = newquad();
  191.     vertex3d_t    *v;
  192.  
  193.     q->n[0] = n[0]; q->n[1] = n[1]; q->n[2] = n[2];
  194.     if (0 == (v = findverthash(v0)))
  195.     v = addvertex(v0);
  196.     q->v0 = v;
  197.     appendpoly((long)q, v);
  198.     if (0 == (v = findverthash(v1)))
  199.     v = addvertex(v1);
  200.     q->v1 = v;
  201.     appendpoly((long)q, v);
  202.     if (0 == (v = findverthash(v2)))
  203.     v = addvertex(v2);
  204.     q->v2 = v;
  205.     appendpoly((long)q, v);
  206.     if (0 == (v = findverthash(v3)))
  207.     v = addvertex(v3);
  208.     q->v3 = v;
  209.     appendpoly((long)q, v);
  210. }
  211.  
  212. void doverts()
  213. {
  214.     long    i;
  215.     vertex3d_t    *vt;
  216.     polylist_t    *p;
  217.     quad_t    *q;
  218.     float    v[3];
  219.     long    vcount;
  220.  
  221.     for (i = 0; i < VERTHASHSIZE; i++) {
  222.     vt = verthashtab[i];
  223.     while (vt) {
  224.         p = (polylist_t *)vt->polys;
  225.         v[0] = v[1] = v[2] = 0.0; vcount = 0;
  226.         while (p) {
  227.         q = (quad_t *)p->data;
  228.         v[0] += q->n[0]; v[1] += q->n[1]; v[2] += q->n[2]; vcount++;
  229.         p = p->next;
  230.         }
  231.         if (v[0] != 0.0 || v[1] != 0.0 || v[2] != 0.0) {
  232.         normalize(v);
  233.         } else v[0] =1.0;    /* XXX hack! XXX */
  234.         vt->n[0] = v[0]; vt->n[1] = v[1]; vt->n[2] = v[2];
  235.         vt = vt->next;
  236.     }
  237.     }
  238. }
  239.  
  240. void doquads(void (*savefunc)())
  241. {
  242.     quad_t    *q = quadlist;
  243.  
  244.     while (q) {
  245.     savefunc(ADD_QUAD, q->v0->n, q->v0->v, q->v1->n, q->v1->v,
  246.                q->v2->n, q->v2->v, q->v3->n, q->v3->v);
  247.     q = q->next;
  248.     }
  249.     cleanupsmooth();
  250. }
  251.  
  252.